package algotithm.leetcode.array.test363;

import java.util.TreeSet;

/**
 * @author 25068
 * @Date 2021/4/22 11:00
 * @Title 363. 矩形区域不超过 K 的最大数值和
 */
public class Solution {

    public static void main(String[] args) {
        int[][] matrix = {{1,0,1}, {0,-2,3}};
        int k = 2;
        Solution solution = new Solution();
        int ans = solution.maxSumSubmatrix(matrix,k);
        System.out.println(ans);
    }

    public int maxSumSubmatrix(int[][] matrix, int k) {
        int n = matrix.length;
        int m = matrix[0].length;
        int ans = Integer.MIN_VALUE;
        for (int i = 0; i < n; i++) {
            int[] sum = new int[m];
            for (int j = i; j < n; j++) {
                for (int t = 0; t < m; t++) {
                    sum[t] += matrix[j][t];
                }
                TreeSet<Integer> set = new TreeSet<>();
                set.add(0);
                int s = 0;
                for (int v : sum) {
                    s += v;
                    Integer ceiling = set.ceiling(s - k);
                    if (ceiling != null) {
                        ans = Math.max(ans, s - ceiling);
                    }
                    set.add(s);
                }

            }
        }
        return ans;
    }


}
